Traditionally, characters have been printed using metal type which allows very detailed rendering of a character, including subtle curves and very fine lines. A character may be alphanumeric, an Oriental or other foreign language character, or even a fanciful design and may be printed in a variety of sizes. In modern computer devices, characters are defined on raster devices such as video display terminals or laser printers or by using a multi-pin print head. Characters can be printed on a surface or displayed on a video screen as a series of dots which are printed or turned on in order to approximate as closely as possible the ideal shape of the character. When characters are small enough relative to the resolution of the display device, choosing which pixels should be displayed to accurately represent the character becomes more complex than when the character is large. A typical video monitor can display about 72 pixels per inch. At this resolution it is difficult to display legibly most type faces smaller than about twenty pixels tall.
An ideal representation of the character is usually defined in "character space" at very high resolution as one or more areas bounded by an outline or path. A character consists of one or more continuous black areas. For instance the letter "O" consists of a single closed loop, the letter "d" consists of a loop connected to a line and the letter "i" consists essentially of a dot a short distance away from a line which may have additional details such as serifs. One way of describing a character involves defining an outline of the outer edge of each contiguous black portion of the character and then filling that outline to display the character. Since characters are usually printed in dark ink on a light background, one can describe filled areas as black but one skilled in the art will recognize that the method of this invention can be used to determine what pixels are candidates for display using any of many fill methods, including characters which are light on a dark background, commonly used in video displays, or characters on backgrounds having a different color. The outline is preferably defined as one or more paths, each of which may be traced either clockwise or counter-clockwise. Each path can be represented as a sequential series of curves and/or linear line segments called edges. If a black area has interior white spaces as, for instance, in the letter "O", each interior white area can also be defined by a path consisting of a series of edges.
When a character is displayed on a raster device, those pixels which fall within the black area of the character should be displayed, that is, they should be printed on a surface or turned on for a video display. At high resolution or when the character is very large, multiple pixels may fall within each black area and the character can be displayed in great detail. When the character is reduced to a small size, however, or the resolution of the device is limited, certain black areas may no longer cover multiple pixels and in fact may cover only a fraction of a pixel. Displaying small characters on a device of limited resolution has been a persistent problem in the past. This is illustrated in FIGS. 1-4 by a character on an 8.times.10 matrix. In FIG. 1 the outline of the character "S" is illustrated as filled at very high resolution. The raster display, however, can only turn on or off entire pixels.
One prior approach to this problem is the center point fill method, illustrated in FIG. 2. A pixel is displayed only if the center of that pixel falls within or on the boundaries of a black area, illustrated by pixels 40-44. Where only a limited number of pixels are available to display the character, there are gaps or dropouts 50-51 in the black areas so that it may be difficult to recognize the character. An alternative way of displaying the character, called area fill, is to turn on all pixels which intersect or fall within the outline of the character. The result, shown in FIG. 3, is that too many pixels are turned on, leading to blobs which also make the character difficult to recognize. At higher resolution both of these methods work successfully but at low resolution characters become difficult to recognize.
One method of resolving these problems is described in U.S. patent application Ser. No. 07-388,336, assigned to the same assignee as the subject invention. That application describes how to turn on pixels with centers that fall within a character black section (center point fill), then to selectively turn on additional pixels to connect each black section if needed (horizontal proximity fill and other methods). The present invention provides a faster method for connecting black sections of a character.